{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Unique Substrings With Equal Digit Frequency"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #counting #hash-function #rolling-hash"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #计数 #哈希函数 #滚动哈希"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: equalDigitFrequency"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #每个数字的频率都相同的独特子字符串的数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "给你一个由数字组成的字符串&nbsp;<code>s</code>，返回<em>&nbsp;</em><code>s</code><em>&nbsp;</em>中<strong>独特子字符串数量</strong>，其中的每一个数字出现的频率都相同<i>。</i>\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> s = \"1212\"\n",
    "<strong>输出:</strong> 5\n",
    "<strong>解释:</strong> 符合要求的子串有 \"1\", \"2\", \"12\", \"21\", \"1212\".\n",
    "要注意，尽管\"12\"在s中出现了两次，但在计数的时候只计算一次。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> s = \"12321\"\n",
    "<strong>输出:</strong> 9\n",
    "<strong>解释:</strong> 符合要求的子串有 \"1\", \"2\", \"3\", \"12\", \"23\", \"32\", \"21\", \"123\", \"321\".\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>解释:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 1000</code></li>\n",
    "\t<li><code>s</code>&nbsp;只包含阿拉伯数字.</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [unique-substrings-with-equal-digit-frequency](https://leetcode.cn/problems/unique-substrings-with-equal-digit-frequency/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [unique-substrings-with-equal-digit-frequency](https://leetcode.cn/problems/unique-substrings-with-equal-digit-frequency/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"1212\"', '\"12321\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalDigitFrequency(self, s: str) -> int:\n",
    "        s_ = set()\n",
    "        ret = 0\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            d = [0] * 10\n",
    "            for j in range(i, n):\n",
    "                c = s[j]\n",
    "                d[int(c)] += 1\n",
    "                b = 0\n",
    "                last_v = None\n",
    "                for ii in range(10):\n",
    "                    if d[ii] == 0:\n",
    "                        continue\n",
    "                    elif last_v is None:\n",
    "                        last_v = d[ii]\n",
    "                    elif last_v != d[ii]:\n",
    "                        b = 1\n",
    "                        break\n",
    "    \n",
    "                if b == 0:\n",
    "                    ss = s[i:j+1]\n",
    "                    if ss not in s_:\n",
    "                        ret += 1\n",
    "                        s_.add(ss)\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalDigitFrequency(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        vis=set()\n",
    "\n",
    "        for start in range(n):\n",
    "            count=Counter()\n",
    "            maxcount=0\n",
    "            max_=0\n",
    "            for end in range(start,n):\n",
    "                count[s[end]]+=1\n",
    "                if count[s[end]]>max_:\n",
    "                    maxcount=1\n",
    "                    max_=count[s[end]]\n",
    "                elif count[s[end]]==max_:\n",
    "                    maxcount+=1\n",
    "                \n",
    "                if maxcount==len(count):\n",
    "                    vis.add(s[start:end+1])\n",
    "        return len(vis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalDigitFrequency(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        vis=set()\n",
    "\n",
    "        for start in range(n):\n",
    "            count=Counter()\n",
    "            maxcount=0\n",
    "            max_=0\n",
    "            for end in range(start,n):\n",
    "                count[s[end]]+=1\n",
    "                if count[s[end]]>max_:\n",
    "                    maxcount=1\n",
    "                    max_=count[s[end]]\n",
    "                elif count[s[end]]==max_:\n",
    "                    maxcount+=1\n",
    "                \n",
    "                if maxcount==len(count):\n",
    "                    vis.add(s[start:end+1])\n",
    "        return len(vis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalDigitFrequency(self, s: str) -> int:\n",
    "        tot = set(s)\n",
    "        n = len(s)\n",
    "        if len(tot) == 1:\n",
    "            return n \n",
    "        vis = set()\n",
    "        ans = len(tot)\n",
    "        for i in range(n - 1):\n",
    "            cnt = Counter([s[i]])\n",
    "            mx = 1\n",
    "            for j in range(i + 1, n):\n",
    "                cnt[s[j]] += 1\n",
    "                if cnt[s[j]] > mx:\n",
    "                    mx += 1\n",
    "                if mx * len(cnt) == j - i + 1:\n",
    "                    vis.add(s[i: j + 1])\n",
    "        return ans + len(vis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    " \r\n",
    "    def equalDigitFrequency(self, s: str) -> int:\r\n",
    "        \"\"\"\r\n",
    "        双指针+计数+集合去重\r\n",
    "        \"\"\"\r\n",
    "        temp_num = set()\r\n",
    "        counter = collections.defaultdict(int)\r\n",
    "        for i in range(len(s)):\r\n",
    "            counter[s[i]] += 1\r\n",
    "            if s[i] not in temp_num:\r\n",
    "                temp_num.add(s[i])\r\n",
    "            for j in range(i + 1, len(s)):\r\n",
    "                counter[s[j]] += 1\r\n",
    "                if len(set(counter.values())) == 1:\r\n",
    "                    if s[i:j + 1] not in temp_num:\r\n",
    "                        temp_num.add(s[i:j + 1])\r\n",
    "            counter.clear()\r\n",
    "        return len(temp_num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalDigitFrequency(self, s: str) -> int:\n",
    "        presum = [[0] * 10 for _ in range(len(s) + 1)]\n",
    "        ans = set()\n",
    "        for i, c in enumerate(s):\n",
    "            for j in range(10):\n",
    "                presum[i + 1][j] = presum[i][j]\n",
    "            presum[i + 1][o] = presum[i][o := ord(c) - ord('0')] + 1\n",
    "            for j in range(i + 1):\n",
    "                m, check = 0, True\n",
    "                for k in range(10):\n",
    "                    if diff := presum[i + 1][k] - presum[j][k]:\n",
    "                        if m and m != diff:\n",
    "                            check = False\n",
    "                            break\n",
    "                        m = diff\n",
    "                if check:\n",
    "                    ans.add(s[j:i+1])\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 前缀和\n",
    "    def equalDigitFrequency(self, s: str) -> int:\n",
    "        presum = [[0] * 10 for _ in range(len(s) + 1)]\n",
    "        ans = set()\n",
    "        for i, c in enumerate(s):\n",
    "            for j in range(10):\n",
    "                presum[i + 1][j] = presum[i][j]\n",
    "                \n",
    "            presum[i + 1][o] = presum[i][o := ord(c) - ord('0')] + 1\n",
    "            for j in range(i + 1):\n",
    "                m, check = 0, True\n",
    "                for k in range(10):\n",
    "                    if diff := presum[i + 1][k] - presum[j][k]:\n",
    "                        if m and m != diff:\n",
    "                            check = False\n",
    "                            break\n",
    "\n",
    "                        m = diff\n",
    "\n",
    "                if check:\n",
    "                    ans.add(s[j:i+1])\n",
    "\n",
    "        return len(ans)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalDigitFrequency(self, s: str) -> int:\n",
    "        \"\"\"Given a digit string s, return the number of unique substrings of s where every digit appears the same number of times.\"\"\"\n",
    "\n",
    "        def check(left: int, right: int) -> bool:\n",
    "            \"\"\"\"[left,right] 这一段子串符合题意\"\"\"\n",
    "            diff = set()\n",
    "            for i in range(10):\n",
    "                count = preSum[right + 1][i] - preSum[left][i]\n",
    "                if count > 0:\n",
    "                    diff.add(count)\n",
    "                if len(diff) > 1:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        n = len(s)\n",
    "        preSum = [[0] * 10 for _ in range(n + 1)]\n",
    "\n",
    "        # 预处理前缀\n",
    "        for i in range(1, n + 1):\n",
    "            preSum[i][ord(s[i - 1]) - ord('0')] += 1\n",
    "            for j in range(10):\n",
    "                preSum[i][j] += preSum[i - 1][j]\n",
    "\n",
    "        res = set()\n",
    "        # 枚举所有子串\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                if check(i, j):\n",
    "                    res.add(s[i : j + 1])\n",
    "\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalDigitFrequency(self, s: str) -> int:\n",
    "        presum = [[0] * 10 for _ in range(len(s) + 1)]\n",
    "        ans = set()\n",
    "        for i, c in enumerate(s):\n",
    "            for j in range(10):\n",
    "                presum[i + 1][j] = presum[i][j]\n",
    "            presum[i + 1][o] = presum[i][o := ord(c) - ord('0')] + 1\n",
    "            for j in range(i + 1):\n",
    "                m, check = 0, True\n",
    "                for k in range(10):\n",
    "                    if diff := presum[i + 1][k] - presum[j][k]:\n",
    "                        if m and m != diff:\n",
    "                            check = False\n",
    "                            break\n",
    "                        m = diff\n",
    "                if check:\n",
    "                    ans.add(s[j:i+1])\n",
    "        return len(ans)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
